contents

점수 기반 부분 문자열 매칭(Scored Subsequence Matching) 은 코드 편집기나 커맨드 라인 도구에서 볼 수 있는 직관적이고 "마음을 읽는 듯한" 느낌의 최신 퍼지 파인더를 구동하는 알고리즘입니다. 이는 쿼리 문자들이 순서에 맞게 존재하는지 확인할 뿐만 아니라, 그 일치 품질에 따라 점수를 부여하여 근사 문자열 일치를 찾는 방법입니다.

점수가 높을수록 더 관련성이 높거나 "더 나은" 일치로 간주됩니다.

두 부분으로 나뉘는 문제

이 알고리즘은 문제를 두 가지 주요 부분으로 나눕니다.

1. 부분 문자열 확인: 대상 문자열이 쿼리 문자들을 올바른 순서로 포함하고 있는가?
2. 점수 시스템: 만약 그렇다면, 그 일치는 얼마나 "좋은가"?

파트 1: 부분 문자열 확인 (전제 조건)

먼저, 알고리즘은 어떤 문자열이 잠재적인 후보인지 아닌지를 결정해야 합니다.

• 부분 문자열(Subsequence)이란? 부분 문자열은 더 큰 문자열 내에서 같은 순서로 나타나지만, 반드시 서로 옆에 붙어 있을(연속적일) 필요는 없는 문자 시퀀스입니다.
  • 예시: 대상 문자열이 application일 때,
    • app은 부분 문자열입니다 (또한 부분 문자열(substring)이기도 함).
    • ali는 부분 문자열입니다.
    • pcn은 부분 문자열입니다 (a**p**pli**c**atio**n**).
    • pna는 글자 순서가 맞지 않으므로 부분 문자열이 아닙니다.

이를 확인하는 것은 간단하고 빠릅니다. 알고리즘은 대상 문자열을 순회하며 쿼리의 각 문자를 순서대로 찾습니다. 대상 문자열의 끝에 도달하기 전에 모든 쿼리 문자를 찾으면 일치하는 것입니다.

파트 2: 점수 시스템 (비법) 🧠

마법이 일어나는 부분입니다. application에 pcn이 유효한 부분 문자열이라고 해서 그것이 좋은 일치라는 의미는 아닙니다. 점수 시스템은 직관적으로 느껴지는 일치에는 보상을 주고 그렇지 않은 일치에는 페널티를 부과하기 위해 일련의 휴리스틱(heuristics) 을 사용합니다.

목표는 대상 문자열을 통과하는 최적의 부분 문자열 경로를 찾아 그 점수를 계산하는 것입니다.

일반적인 점수 휴리스틱

• 연속 일치 보너스: 가장 높은 보상입니다. 쿼리의 문자들이 대상에서 연속적으로 나타나면 큰 보너스를 받습니다.
  • 쿼리: app
  • 대상: **app**le.js (app에 대한 큰 보너스)는 **a**bout_**p**age_tem**p**late.js보다 훨씬 높은 점수를 받습니다.
• 단어 경계 보너스: 단어의 시작이나 구분 문자(예: _, -, /, .) 뒤에 오는 일치에 보너스가 주어집니다. 이것이 약어가 잘 작동하는 이유입니다.
  • 쿼리: ac
  • 대상: **a**pp_**c**ontroller.rb (두 번의 단어 경계 보너스)는 훌륭한 일치입니다.
• 대문자 일치 보너스: 카멜 케이스(camelCase) 문자열에서 대문자와 일치하면 보너스를 받습니다. 이 덕분에 FSB라는 쿼리로 **F**ile**S**ystem**B**uffer와 같은 클래스를 매우 효과적으로 검색할 수 있습니다.
• 간격 페널티: 일치하는 문자 사이에서 건너뛴 대상 문자열의 모든 문자에 대해 페널티가 적용됩니다.
  • 페널티는 종종 간격의 크기가 클수록 증가하므로, 작은 건너뜀은 큰 건너뜀보다 페널티가 적습니다.
  • 쿼리: app
  • 대상: **a**bc**p**defghi**p는 매우 높은 간격 페널티를 받아 낮은 점수를 받을 것입니다.
• 첫 글자 보너스: 대상 문자열의 바로 첫 글자와 일치하는 경우 종종 보너스가 주어집니다.

구현 방식 (상위 레벨)

가능한 모든 부분 문자열 경로 중에서 최고 점수를 찾는 것은 고전적인 동적 프로그래밍(dynamic programming) 문제입니다.

구현 방식은 다양하지만, 일반적인 접근 방식은 행이 쿼리 문자를, 열이 대상 문자열의 문자를 나타내는 2D 행렬을 만드는 것입니다. 알고리즘은 이 행렬을 통과하며, 각 셀 (i, j)에는 쿼리의 첫 i개 문자가 대상의 첫 j개 문자 내에서 일치할 때 얻을 수 있는 최상의 점수가 저장됩니다.

새 셀의 값을 계산할 때, 알고리즘은 이웃 셀들의 점수를 고려하고 휴리스틱을 적용합니다.

• "현재 문자 query[i]와 target[j]를 일치시키면 점수가 어떻게 될까?" (연속/경계 일치에 대한 보너스 적용).
• "현재 target[j]를 일치시키지 않으면 점수가 어떻게 될까?" (간격 페널티 적용).

알고리즘은 점수를 최대화하는 경로를 선택하며, 최종 점수는 행렬의 마지막 행에서 찾을 수 있습니다.

결론적으로, 점수 기반 부분 문자열 매칭은 현대 퍼지 파인더의 직관적인 느낌을 가능하게 하는 정교한 알고리즘입니다. 단순한 일치 여부를 넘어, 정교한 보너스 및 페널티 규칙을 적용하여 단순히 _일치하는지_가 아니라 얼마나 좋은 일치인지를 결정하며, 이를 통해 현대 개발 도구에서 볼 수 있는 빠르고 너그러운 검색 경험을 제공합니다.

references